package arthur;

import java.util.Random;

public class quickSort2 {

	public int[] quickSort(int A[], int comecoDoArray, int fimDoArray) {
		if (comecoDoArray < fimDoArray) {
			selecinarPivo(A, comecoDoArray, fimDoArray);
			int q = patition(A, comecoDoArray, fimDoArray);

			quickSort(A, comecoDoArray, q - 1);
			quickSort(A, q + 1, fimDoArray);
		}
		return A;
	}

	private void selecinarPivo(int[] a, int comecoDoArray, int fimDoArray) {
		Random random = new Random();
		int variacao = ((fimDoArray - comecoDoArray) + 1);
		int posicionOfPivo = random.nextInt(variacao);
		posicionOfPivo += comecoDoArray;
		swap(a, fimDoArray, posicionOfPivo);
	}

	
	private int patition(int[] a, int comecoDoArray, int fimDoArray) {

		int pivo = a[fimDoArray];
		int i = comecoDoArray - 1;

		for (int j = fimDoArray - 1; j > i; j--) {
			if (a[j] < pivo) {
				i++;
				swap(a, j, i);
				j++;
			}
		}
		swap(a, fimDoArray, i+1);
		return i+1;
	}

	private void swap(int[] a, int j, int i) {
		int temp = a[j];
		a[j] = a[i];
		a[i] = temp;

	}
}